#include <iostream>
#include "gtest\gtest.h"
#include "dist.h"
#include <vector>
#include <cstdlib>
#include <assert.h>
#include <time.h>
#include <functional>

template<class T>
int getDistance(const std::vector<T> &x, const std::vector<T> &y){
	std::vector<std::vector<int> > d(x.size() + 1, std::vector<int>(y.size() + 1));
	for (int j = 1; j <= y.size(); ++j)
		d[0][j] = j;

	for (int i = 1; i <= x.size(); ++i)
		d[i][0] = i;

	for (int i = 1; i <= x.size(); ++i)
	for (int j = 1; j <= y.size(); ++j)
	if (x[i - 1] == y[j - 1])
		d[i][j] = d[i - 1][j - 1];
	else
		d[i][j] = std::min(1 + d[i - 1][j], 1 + d[i][j - 1]);

	return d[x.size()][y.size()];
}

bool doesReciepeGetToFromFrom(const std::vector<std::string> &from, const std::vector<std::string> &to, const std::vector<int> &recipe) {
	int i = 0, j = 0;
	for (auto action:recipe){
		if (action == 0){

			if (i >= from.size())
				return false;

			if (j >= to.size())
				return false;

			if (from[i] != to[j])
				return false;

			i++, j++;
		}
		if (action == -1)
			++i;
		if (action == 1)
			++j;
	}

	if (i != from.size() || j != to.size())
		return false;

	return true;
}

std::string getRandString(){
	std::string exmpl[] = { "pineapple", "cherry", "strawberry", "bilberry", "cranberry", "raspberry" };
	return exmpl[rand() % 6];
}

template<typename T>
std::vector<T> getFilledVector(int lenght, std::function<T(int)> func){
	std::vector<T> ans(lenght);
	for (int i = 0; i < lenght; ++i)
		ans[i] = func(i);
	return ans;
}

void runSpeedTest(){
	int n = 100000;
	std::vector<int> common_part = getFilledVector<int>(n, [](int x){ return rand() % 1000;  });

	std::function<int(int)> generator = 
		[common_part](int x){
			if (rand() % 100 == 0)
				return rand() % 1000;
			else
				return common_part[x];
		};

	std::vector<int> text1 = getFilledVector<int>(n, generator);
	std::vector<int> text2 = getFilledVector<int>(n, generator);

	clock_t start, end;
	start = clock();
	int difference = DistanceFounder::getDistance(text1, text2);
	end = clock();


	std::cout << "Worktime on texts with length 10^5 and difference " << difference << " is ";
	std::cout << 1.0*(end-start)/CLOCKS_PER_SEC << "\n";
}

TEST(VectorWithNegativeIndices, general){
	int n = 10;
	VectorWithNegativeIndices a(n);
	for (int i = -n; i <= n; ++i)
		a[i] = i;
	for (int i = -n; i < n; ++i)
		EXPECT_EQ(i, a[i]);
}

TEST(getLongestCommonPrefixLength, handle){ 
	
	int first[] = { 1, 2, 3, 4, 5 };
	int second[] = { 1, 2, 3, 7, 10 };
	std::vector<int> a(first, first + 5), b(second, second + 5);

	EXPECT_EQ(3, getLongestCommonPrefixLength(a.begin(), a.end(), b.begin(), b.end()));
	EXPECT_EQ(0, getLongestCommonPrefixLength(a.begin()+1, a.end(), b.begin(), b.end()));
	EXPECT_EQ(2, getLongestCommonPrefixLength(a.begin()+1, a.end(), b.begin()+1, b.end()));

	
}

TEST(DistanceFounder, getDiagonalLength){
	

	EXPECT_EQ(2, DistanceFounder::getDiagonalLength(2, 2, 0));
	EXPECT_EQ(1, DistanceFounder::getDiagonalLength(1, 10, -5));
	EXPECT_EQ(3, DistanceFounder::getDiagonalLength(10, 10, 7));
}

TEST(DistanceFounder, setPositionOnDiagonal){
	
	int p1, p2;

	DistanceFounder::setPositionOnDiagonal(1, 1, 10, 10, p1, p2);
	EXPECT_EQ(2, p1);
	EXPECT_EQ(1, p2);

	DistanceFounder::setPositionOnDiagonal(0, 2, 13, 17, p1, p2);
	EXPECT_EQ(2, p1);
	EXPECT_EQ(2, p2);

	DistanceFounder::setPositionOnDiagonal(-2, 3, 13, 19, p1, p2);
	EXPECT_EQ(3, p1);
	EXPECT_EQ(5, p2);
}

TEST(DistanceFounder, getDistanceHandle){
	
	{
		int a[] = { 2, 3, 7, 8 };
		int b[] = { 3, 7, 8 };
		std::vector<int> v1(a, a + 4);
		std::vector<int> v2(b, b + 3);

		EXPECT_EQ(1, DistanceFounder::getDistance(v1, v2));
	}

	{
		int a[] = { 0 };
		int b[] = { 0 };
		std::vector<int> v1(a, a + 1);
		std::vector<int> v2(b, b + 1);

		EXPECT_EQ(0, DistanceFounder::getDistance(v1, v2));
	}

	{
		int a[] = { 1, 2 };
		int b[] = { 2, 1 };
		std::vector<int> v1(a, a + 2);
		std::vector<int> v2(b, b + 2);

		EXPECT_EQ(2, DistanceFounder::getDistance(v1, v2));
	}

	{
		int a[] = { 1, 3, 5, 7 };
		int b[] = { 3 };
		std::vector<int> v1(a, a + 4);
		std::vector<int> v2(b, b + 1);

		EXPECT_EQ(3, DistanceFounder::getDistance(v1, v2));
	}

	{
		int a[] = { 4, 5 };
		int b[] = { 1, 2, 5, 4, 5, 10, 11 };
		std::vector<int> v1(a, a + 2);
		std::vector<int> v2(b, b + 7);

		EXPECT_EQ(5, DistanceFounder::getDistance(v1, v2));
	}

}

TEST(DistanceFounder, getDistanceStress){
	for (int tests = 0; tests < 10; ++tests){
		std::vector<int> v1 = getFilledVector<int>(rand() % 100 + 10, [](int x){return rand() % 20; });
		std::vector<int> v2 = getFilledVector<int>(rand() % 100 + 10, [](int x){return rand() % 20; });

		int ans = getDistance(v1, v2);
		EXPECT_EQ(ans, DistanceFounder::getDistance(v1, v2));//link version
		EXPECT_EQ(ans, DistanceFounder::getDistance(v1.begin(),v1.end(),v2.begin(),v2.end()));//Iterator version
	}
}

TEST(DistanceFounder, Integration){
	
	for (int i = 0; i < 10; ++i){
		
		std::vector<std::string> v1 = getFilledVector<std::string>(rand() % 1000 + 10, [](int x){return getRandString(); });
		std::vector<std::string> v2 = getFilledVector<std::string>(rand() % 1000 + 10, [](int x){return getRandString(); });



		std::vector<int> ans = DistanceFounder::diff(v1, v2);

		EXPECT_TRUE(doesReciepeGetToFromFrom(v1, v2, ans)); //it's sufficient.
		//correctness of lenght of ans checked in (DistanceFounder,getDistanceHandle) and (DistanceFounder,getDiastanceStress)
	}


}

void handle(){
	int n, m;
	std::cin >> n >> m;
	std::vector<std::string> v1(n), v2(m);
	for (int i = 0; i < n; ++i)
		std::cin >> v1[i];
	for (int i = 0; i < m; ++i)
		std::cin >> v2[i];
	
	
	std::vector<int> ans = DistanceFounder::diff(v1, v2);

	std::cout << doesReciepeGetToFromFrom(v1, v2, ans) << "!\n";
}

int main(int argc, char ** argv){
	srand(17);
	runSpeedTest();
	::testing::InitGoogleTest(&argc,argv);
	return RUN_ALL_TESTS();
}